Round Overview
Discuss this match
Used as: Division Two - Level One:
Value | 250 |
Submission Rate | 897 / 970 (92.47%) |
Success Rate | 722 / 897 (80.49%) |
High Score | sachin92 for 249.89 points (0 mins 35 secs) |
Average Score | 206.65 (for 722 correct submissions) |
This problem’s format allowed plenty of different solutions. The challenge was in finding one that is both simple and fast to code, to prove and correct. So you can extract the most points from it.
We should find integer solutions to the equation ab + c = y
, the integers should not be 0 or 1. This is to avoid incredibly trivial solutions such as a = b = c = 0
. But we can still reach some nice small solutions. There are many solutions to ab + c = y
. For example, what if ab
was fixed? Then we would need c = y - ab
.
There is a problem with c = y - ab
, and it is that there may be values of y
that yield c = 0
or c = 1
, so we need to pick ab
in the best way possible. We want y - ab != 1
and y - ab != 0
. This is when we get clever, imagine a = 2, b = 2
, we have y - ab = y - 4
. The problem with y - 4
is that when y = 4
we have y - 4 = 0
and when y = 5
, y - 4 = 1
. This wouldn’t be an issue if we had y + 4
, right? Well, it turns out that we can definitely have y + 4
, just make one of a
or b
negative: a = 2, b = -2
. Then c = y + 4
. So for any y
, a = 2, b = -2, c = y + 4
solves the equation and is an answer.
In other words, just write a solution that returns this vector: {2,-2,y+4}
.
1
2
3
4
5
6
7
vector < int > makeExpression(int y) {
return {
2,
-2,
y + 4
};
}
Or a similar solution in python:
1
2
3
class AddMultiply:
def makeExpression(self, y):
return (-1, 2, y + 2)
Alternative solutions and additional comments.
<Place your comments here>
IncrementingSequence
Problem Details
Used as: Division Two-Level Two:
Value | 500 |
Submission Rate | 729 / 970 (75.15%) |
Success Rate | 424 / 729 (58.16%) |
High Score | wlzhanga123 for 486.02 points (4 mins 50 secs) |
Average Score | 347.78 (for 424 correct submissions) |
The crux of the matter is to assign each element in the input to a target number in the permutation (Numbers from 1 to N
).
A first wrong intuition is to sort the numbers and assign the smallest element to 1, the second -smallest to 2 and so and so. This is not a good approach. Because we are only allowed to add multiples of k
to the elements to convert them into the target numbers. So if we want to turn an element x
into target number y
we must follow two conditions: a) x <= y
and x = y mod k
. (For example, x mod k = y mod k
, if divide both x and y by k
, the remainder should be the same. This is modular arithmetic. We can also just do a loop and increase x
by k
until it becomes greater than or equal to y
, if it becomes greater, then we can’t make x
so large.
The issue is that if we just sort the sequence, we might miss some corner cases, for example: 1,1,2
with K = 2
. It doesn’t make any sense to assign the second 1
to become number 2, it is better to make it become number 3.
The trick is to consider the assignments in the other way. First we search for an element x
that should become 1
. then 2
, then 3
and so and so. First we assign something to 1, it makes sense to pick a 1 element, but a more general way to phrase this is to pick the smallest element x
such that x <= 1
and x mod k = 1 mod k
. Then we should find an element for 2, we repeat that logic: smallest x <= 2
such that x mod k = 2 mod k
, note that if k = 1
, then x
may be 1. The same for target i
, find the smallest x <= i
such that i mod k = x mod k
. We should never reuse an element we already assigned. This approach is correct because we always assign the smallest possible element.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
string canItBeDone(int k, vector < int > A) {
int n = A.size();
sort(A.begin(), A.end());
for (int i = 1; i <= n; i++) {
// pick one x for i
bool valid = false;
for (int j = 0;
(j < n) && !valid; j++) {
if ((A[j] <= i) && (A[j] % k == i % k)) {
A[j] = 1000; //by doing this we ensure A[j] won't be picked again
valid = true;
}
}
if (!valid) {
return "IMPOSSIBLE";
}
}
return "POSSIBLE";
}
A similar approach is to split the sequence in such a way that for each i < k
, there is a group of elements equal to i mod k
. Then we can solve for each of these individually. For example, for k = 2, N = 9
, we should assign values for 1,3,5,7,9
and 2,4,6,8
separately, and each group of values get groups of x
that might be valid. For each of them, we assign the smallest x
to the smallest possible value.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class IncrementingSequence:
def canItBeDone(self, k, A):
A = list(A)
def can(x, t):
return x <= t and x % k == t % k
def modi(i):
s = sorted([x
for x in A
if x % k == i % k])
return all((i + j * k <= len(A)) and can(si, i + j * k) for (j, si) in enumerate(s))
res = all(modi(i) for i in range(1, k + 1))
return "POSSIBLE"
if res
else "IMPOSSIBLE"
ConundrumReloaded
Problem Details
Used as: Division Two - Level Three:
Value | 950 |
Submission Rate | 173 / 970 (17.84%) |
Success Rate | 33 / 173 (19.08%) |
High Score | WoYaoPiaoChang for 804.79 points (12 mins 32 secs) |
Average Score | 529.04 (for 33 correct submissions) |
Let’s start simple and assume there are no question marks. Everybody in the circle has been asked the question.
This case is easy to solve by simulating two things: a) What happens if friend i
is honest and b) What happens if friend i
is a liar. This works for any i
, let’s just use i = 0
. If friend 0 is honest and friend 0’s answer was H, this means that friend 1 must be honest too, if 0’s answer was L it means friend 1 must be a liar. And so and so, knowing that friend i
is honest or not combined with their answer will tell us if friend i+1
is honest or not and we can repeat with i+2
, etc.
The friends make a circle, which means that eventually you will know if friend n -1
is honest or not and this friend will have an answer about friend 0. From this we can infer if friend 0 is honest or not. There is a catch: This may lead to a contradiction. If we assumed friend 0 was honest, but eventually we can conclude that friend 1 is lying, then this is a contradiction and the case is inconsistent. It may also be possible that we assumed friend 0 to be a liar but we reach the conclusion that they are honest. Another contradiction.
When there are no contradictions, then we already know of a possible scenario. There are at most two scenarios here (either friend 0 is a liar or not), and so we can just simulate them bot. If a scenario doesn’t lead to a contradiction, then its number of liars can be a result. Remember the smallest valid number of liars.
In another case, there is at least one question mark in the input. Let’s say friend i
has a question mark. This means that we never asked friend i
about friend (i+1) mod n
.
Let’s try a simple case for now:
i i+1 i+2 i+3 i+4
? H L H H ?
There is a string “HLHH” starting at index i
and it is surrounded by question marks. For now we will ignore the cyclic nature of the circle of friends.z
Whatever friend i
is, a liar or a honest person, it will not cause an effect on person i
. We can decide i
to be a liar or not and just ignore person i -1
. So we can do it, we can simulate the case when i
is honest and the case when i
is a liar. The simulation is the same as before, if i
is a liar and their answer was H, then i+1
is also a liar. Eventually we will reach a conclusion about i+4
. So by simulating this string, we can find conclusions about i, i+1, i+2, i+3
and even i+4
. Note that i+4
won’t have an effect on i+5
What about cycles?
0 1 2 n-2 n-1
H H ? ... ? H L
In this case, there is a substring HLHH, in n -2, n -1, 0, 1
. But it is easy to see that if you just simulate this substring it will be the same as before, you will be able to find a conclusion about n -2, n -1, 0,1,2
.
In a corner case, there is only one question mark: “HH?HL”. This is also not a problem, the string “HLHH” determines the liars in all the indexes and there are no issues with contradictions, because if i=2
is a liar or not, it doesn’t affect i=3
.
When there are too many contiguous ? together: “HH?**???**HL” we can find that we won’t be able to find a conclusion for many of the indexes with question marks (The ones in bold text). Fear not, because we can just assume they are all honest people (we want to minimize the number of liars, remember). If they are all honest people, everything else will remain consistent.
In short, in order to solve this case, we need to extract each substring of contiguous non -question marks, also notice that we need to be careful about the cyclic nature of the string. For example: “H??LLL??HLHL???L” becomes about solving strings: “LLL?”, “HLHL?” and “LH?” separately. In each of them, we can decide if the first person (in the substring) is a liar or not and then pick the minimum number of liars.
##Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
const int INF = 1000;
int minimumLiarsLine(string answers) {
int n = answers.size();
int res = INF;
for (int v = 0; v < 2; v++) {
bool honest0 = (v == 0);
bool prev = honest0;
int liars = (honest0 ? 0 : 1);
for (int i = 1; i <= n; i++) {
bool tru = (answers[i - 1] == 'H');
if (!prev) {
tru = !tru;
}
if (!tru) {
liars++;
}
prev = tru;
}
res = std::min(res, liars);
}
return res;
}
int minimumLiars(string answers) {
int res = INF;
int n = answers.length();
int q = -1;
for (int i = 0; i < n; i++) {
if (answers[i] == '?') {
q = i;
}
}
if (q == -1) {
//cyclic case
// Either 0 is a liar or honest, consistent?
for (int v = 0; v < 2; v++) {
bool honest0 = (v == 0);
bool prev = honest0;
int liars = 0;
bool consistent = false;
for (int i = 1; i <= n; i++) {
bool tru = (answers[i - 1] == 'H');
if (!prev) {
tru = !tru;
}
if (!tru) {
liars++;
}
if (i == n) {
consistent = (tru == honest0);
}
prev = tru;
}
if (consistent) {
res = std::min(res, liars);
}
}
} else {
// I miss yield :(
string curr = "";
res = 0;
for (int i = 0; i <= n; i++) {
int j = (q + i) % n;
if (answers[j] == '?') {
if (curr != "") {
res += minimumLiarsLine(curr);
}
curr = "";
} else {
curr = curr + answers[j];
}
}
res = std::min(res, INF);
}
if (res >= INF) {
res = -1;
}
return res;
}
In the following python solution, we manage to use the same sub-routine to simulate both the cyclic and line case:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
import itertools
class ConundrumReloaded:
def minimumLiars(self, answers):
def simulateLine(f, s):
p = f
liars = 0
for i in range(1, len(s) + 1):
h = (s[i - 1] == 'H') ^ (not p)
liars += not h
p = h
return (liars, p)
n = len(answers)
q = -1
for i in range(n):
if answers[i] == '?':
q = i
INF = 10 ** 9
res = INF
if q == -1:
for f in (0, 1):
(liars, p) = simulateLine(f, answers)
if p == f:
res = min(res, liars)
else:
res = 0
curr = ''
for i in range(n + 1):
j = (i + q) % n
if answers[j] == '?':
if curr != '':
res += min((not f) + simulateLine(f, curr)[0]
for f in (0, 1))
curr = ''
else:
curr = curr + answers[j]
return -1
if res >= INF
else res
PalindromePermutations
Problem Details
Used as: Division One - Level One:
Value | 250 |
Submission Rate | 671 / 717 (93.58%) |
Success Rate | 489 / 671 (72.88%) |
High Score | LayCurse for 245.37 points (3 mins 54 secs) |
Average Score | 179.83 (for 489 correct submissions) |
The approach we’ll take is to calculate the probability as the number of palindrome anagrams divided by the total number of anagrams.
We should find the total number of anagrams of a string word possibly containing repeated letters. The number of permutations of something with repetitions is a known -formula. Basically, the formula without repetitions is, of course, n!
(The factorial). If there was a character that gets repeated m _0
times, then we should divide that result by m _0!
. If another letter got repeated m _1
times, divide by m _1!
and so and so…
The numerator is more complicated because we need to make sure the counted anagrams are palindromes. This requires different treatment if the length n
is even or odd.
If the string has even length then we can tell that each letter in one side of the string will have an equivalent letter in the opposite side. For example: “abbcaacbba”. The idea here is that the first half: “abbca” determines the order in the other half. So there are only as many anagrams as correct ways to order the first half. For each letter a
present m _a
times in the word, the first half should have exactly m _a / 2
times that letter. The first half also has n/2
length. Now we can just use the formula we used for the denominator: This time we have (n/2)!
divided by : | _ _m _i / 2 _ _|!
for each letter i
present m _i
times in the word. ( | _ _x _ _|
is the floor of x
).
If one letter exists an odd number of times in the word, then it is impossible to have any palindrome anagram, the probability is 0.
This time exactly one letter must appear an odd number of times, like “c” in: “abbcacacbba”. This letter must forcefully be placed at the center of the palindrome. Otherwise we have exactly the same situation, the first half determines the second half. You will find the formula is exactly the same: (n/2)!
divided by : | _ _m _i / 2 _ _|!
for each letter i
present m _i
times in the word. It helps that we are using the floor function. (Since they are integers, a single integer division will suffice)
We just need to detect the case when the number of odd letters is different to 1 and return 0.0 in that case.
We just need to calculate the factorials and then count the number of times each letter appears and perform divisions. We can use doubles in all operations, 64 bits floating point variables should be able to hold even 50!
and all we do before the final division is product and addition which are stable.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
double palindromeProbability(string word) {
int n = word.size();
// precalculate factorials f[n] = n!
double f[n + 1];
f[0] = 1.0;
for (int i = 1; i <= n; i++) {
f[i] = i * f[i - 1];
}
// p / q
double p = f[n / 2], q = f[n];
int odd = 0;
// for each letter:
for (char ch = 'a'; ch <= 'z'; ch++) {
int t = count(word.begin(), word.end(), ch);
if (t % 2 == 1) { //count the number of odd letters
odd++;
}
// divide numerator by (t / 2)!
p /= f[t / 2];
// divide denominator by t!
q /= f[t];
}
// handle special cases:
if ((odd > 1) || (odd != n % 2)) {
return 0.0;
}
return p / q;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class PalindromePermutations:
def palindromeProbability(self, word):
# calculate the factorial of n as a double, we don 't use the library
# version because it uses integers
def f(n):
return 1.0
if n <= 0
else n * f(n - 1)
n = len(word)
# find all the letters that appears an odd number of times
odd = [ch
for ch in set(word) if word.count(ch) % 2 == 1]
if (len(odd) > 1) or((len(odd) == 1) != (n % 2 == 1)):
return 0.0 #handle special wrong cases
(p, q) = (f(n / 2), f(n))
for ch in set(word): #
for each letter that appears in word(without repeating it)
t = word.count(ch) # count the number of times it appears
p /= f(t / 2)
q /= f(t)
return p / q
BlockTheBlockPuzzle
Problem Details
Used as: Division One - Level Two:
Value | 500 |
Submission Rate | 185 / 717 (25.80%) |
Success Rate | 99 / 185 (53.51%) |
High Score | sdya for 460.78 points (8 mins 26 secs) |
Average Score | 270.53 (for 99 correct submissions) |
A good first step is to understand the special rules that limit the allowed moves. “In other words, the block must always be rolled over an edge of length 1.”. After some analysis you should come to the following conclusion: The reachable positions follow this pattern:
The 1x1 colored (blue) areas are where the block can be put on with the 1x1 face touching the board. The horizontal 2x1 (red) colored areas are where the block can reach with the 2x1 face touching the board horizontally. The vertical 1x2 colored areas (green) are were the 2x1 face of the block can touch, but this time vertically. The cell tagged ‘b’ is the starting location. It is interesting to see that all 1x1 cells that are reachable follow a pattern of distances of 3 from the initial cell. Formally, if the initial cell is (i,j)
, then cell (x,y)
can be reached only if x -= i mod 3
and y -= j mod 3
.
Imagine if the exit cell didn’t fall in one of those blue / reachable 1x1 cells. Then the exit cell would not be reachable at all. Because the problem statement requires the the 1x1 face of the block touches it. This means we can ignore all those start cells. The game is already unsolvable if you pick those start cells, so there is no reason to block them.
The rest is to consider the game as a graph. There are many ways to do this, but perhaps the most practical is to consider only cells that may reach the goal (have coordinates (x,y)
such that x -= g _x mod 3
and y -= g _y mod 3
, where (g _x,g _y)
is the goal cell) as vertices. The 2x1 areas can be seen as edges. Some cells are blocked (contain a hole), and some edges are blocked too (both of their cells are holes). So playing the game equals to picking one of the starting cells and finding a path in this graph towards the goal cell (a vertex).
The problem is then to find the minimum cost to make any path from a starting cell to the goal cell impossible. This is really the minimum cut problem. But we need to deal with a couple of specifics of how to reduce this problem to minimum cut.
The first issue is that there may be multiple starting cells, whereas the minimum cut problem has only a start and a goal. The trick here is to create a global start VERTEX (source) that is directly connected to all the vertices that represent start cells. If we cut all paths from this starting vertex to the goal, we cut all possible paths. It should not be possible to remove the edges connecting this special start vertex to the cells, so these edges should have an infinite (very large) cost to be removed.
Another issue: We can add holes to both 1x1 cells and the 2x1 “edges” connecting them. The minimum cut problem only supports cutting edges, not vertices. However, with a simple modification we can enable vertex cutting. This modification is described in the topcoder max flow tutorial. Just create two vertices for each 1x1 cell. An entry vertex and an exit vertex. An edge (that can be removed) connects the entry and exit vertices. The cost to remove this edge should be the cost to turn the cell into a hole.
The edge costs: When there is no hole in a 1x1 cell, the cost to remove it is 1. When there are no holes in a 2x1 edge, the cost to remove it is 2. If there is only one hole, the cost is 1. If there are two holes, the edge is already removed.
Finally, some edges and cells cannot really be removed. This happens when the cell is a start/goal cell or when the edge contains a start cell. In this case, the cost to remove the edge/cell should be infinite (If we are talking about a 1x1 cell, then the edge connecting its entry and exit vertices should be infinite).
To solve the minimum cut problem, we can reduce the graph into a flow network. Turn the start and final vertices into sink and source and the edge removal costs into capacities. The maximum flow will be the minimum cost to cut the paths between the source and sink. This is the minimum cut theorem.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
const int INF = 20;
const char GOAL = '$';
const char HOLE = 'H';
const char START = 'b';
const char NORMAL = '.';
// This code makes use of an external max flow library that is not included here
// The max flow solver is presented as a class "network" that allows you to
// create vertices and edges with capacities in the network. The maxFlow() method
// returns its maximum flow.
int minimumHoles(vector < string > board) {
int n = board.size();
int gx = 0, gy = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (board[i][j] == GOAL) {
gx = i;
gy = j;
}
}
}
MaxFlow::network * G = new MaxFlow::network();
G - > source = G - > addVertex();
G - > sink = G - > addVertex();
int vIn[n][n];
int vOut[n][n];
for (int i = gx % 3; i < n; i += 3) {
for (int j = gy % 3; j < n; j += 3) {
if (board[i][j] != HOLE) {
vIn[i][j] = G - > addVertex();
vOut[i][j] = G - > addVertex();
if (board[i][j] == NORMAL) {
// can put a hole here
G - > addEdge(vIn[i][j], vOut[i][j], 1);
} else {
G - > addEdge(vIn[i][j], vOut[i][j], INF);
}
if (i == gx && j == gy) {
G - > addEdge(G - > source, vIn[i][j], INF);
}
if (board[i][j] == START) {
G - > addEdge(vOut[i][j], G - > sink, INF);
}
}
}
}
for (int i = gx % 3; i < n; i += 3) {
for (int j = gy % 3; j < n; j += 3) {
int dx = 0, dy = -1;
for (int r = 0; r < 4; r++) {
int nx = i + 3 * dx, ny = j + 3 * dy;
if ((0 <= nx && nx < n) && (0 <= ny && ny < n) &&
(board[nx][ny] != HOLE) &&
(board[i][j] != HOLE)) {
char s1 = board[i + dx][j + dy];
char s2 = board[i + 2 * dx][j + 2 * dy];
int cap = 0;
if (s1 == START || s2 == START) {
cap = INF;
} else {
if (s1 == NORMAL) {
cap++;
}
if (s2 == NORMAL) {
cap++;
}
}
G - > addEdge(vOut[i][j], vIn[nx][ny], cap);
}
int z = dy;
dy = dx;
dx = -z;
}
}
}
int f = G - > maxFlow();
delete G;
if (f >= INF) {
return -1;
} else {
return f;
}
}
Used as: Division One - Level Three:
Value | 900 |
Submission Rate | 24 / 717 (3.35%) |
Success Rate | 16 / 24 (66.67%) |
High Score | Dmitry_Egorov for 696.46 points (16 mins 23 secs) |
Average Score | 523.79 (for 16 correct submissions) |
Imagine we just kept the circle of friends. We just add friend “A” to some position. Then “B”, then “C”, making sure there are never more than G
clusters. Each state will look like a string “…A…BD.C”. We could try a function f(S, k)
where S
is the state and k
the number of friends already added. Which counts the number of final setups after we add the remaining K - k
friends. The objective is to simplify the states to reduce their total number.
A first idea is to note the setup is cyclic. So states “A…CB.” and “…CB.A” are equivalent. The number of ways to position the remaining friends will be the same. One thing we can do is consider only cases in which “A” is placed in the first position, if we do this, the total we find should be multiplied by N
to account for the possible starting locations of A
.
We are counting the total number of final setups that can be reached without breaking the cluster rule. As the statement says, if G = 1
, then “ACB.” is not possible. One important factor here is the order of the friends in the state. “ACB.” is impossible, but “ABC.” is possible. Different orders will imply different final setups. In a way we are counting the number of different ways to order the friends.
We need more than just the order though. A final state “A.B.C.” might be impossible whilst “AB.C.” is possible (One has more clusters). We should keep in consideration the gaps between the friends.
However, consider these two cases: “A…B.” and “A.B…”. The distance between A and B varies. What does not vary is the number of clusters. In fact, the number of clusters in each step is also the same: First we have a cluster with A then we add a new cluster containing B. This is true for any pair of states in which the relative order of friends is the same and the separations exist between the same friends, the length of the separations does not change if the state is reachable or not: If “A…CB…D…FE.” is reachable, then “A.CB.D.FE…” is also reachable.
Let’s simplify states once again. This time we use " *" to mean there is a separation between the friends. So “A *B” with N = 7
may represent states “A.B…”, “A…B…”, “A…B…” and “A…B.”. (note that “A…B” is a different thing altogether). Our main concern when we reach a final setup “A *DC *B” is that it is possible to reach the setup without breaking the rules. The lengths of the gaps don’t matter too much for that objective.
There are two issues to note here: After we decide the order and gaps for all the friends, we should count the total number of final positions that follow that pattern. Also we need to understand how the patterns are built.
We start with “A” as the pattern. The first friend is just in their position. When we add a friend “B” we have many options:
We can place B in a new cluster: “A *B” note that “B *A” would be the same situation, just rotated.
We can place B in the same cluster: “AB” or “BA”. Note that depending on N
what this patterns mean varies: If N = 3
, these patterns mean: “AB.” and “A.B”, two different things. But if N = 2
, these patterns both mean “AB”.
Assume we pick “A *B” now we need to add friend “C”.
We can place “C” as a new cluster. Note that we do not know much about the length of the gap between A and B. We know that there is also a separation between “B” and “A” (Else the pattern would be just “BA”). There are two separations each should have a length of at least 1. The sum of their lengths cannot exceed N - 2
. The maximum length of a gap in this case is N - 1
. If the gap between “A” and “B” could be 3, then we can place C between them: “A *C *B”, note that this increments the number of groups, so if it exceed G
, it is illegal. We could also place C between B and A: “A *B *C”.
If the length of the a gap could be 2 or more, then we can place C right next to one of the clusters. Like “CA *B”, “AC *B”, “A *CB” and “A *BC”.
Maybe the gaps have length 1 and then we can use “C” to merge the clusters: “ACB” or “ABC”.
Imagine we conclude that it is possible to reach pattern “A *CB *D”. We have N = 9
. How many final setups does this pattern represent? We should count all the number of ways to have that order A -C -B -D, using those separators. There are three separations: Between A and C, between B and D and between D and A. The number of empty spaces will be 9 - 4 = 5
. We need to distribute 5
empty spaces between 3 separations, in such a way that each separation contains at least one empty space. This is a combinatorics problem: Count the number of ways to distribute s
elements between t
slots in such a way that each slot contains at least one element. The result is ((s -1),(t -1))
, where ((n),(k))
is the binomial coefficient. (The problem is reduced to mixing t -1
separators and s -t
elements together).
Isn’t it convenient the formula depends on only two things? a) The number of friends and b) The number of clusters.
Ultimately, patterns like “A *BC”, “A *CB”, “AB *C” and “AC *B” will all yield the same result.
A different relative order and position of gaps yields a different group of final setups. However, we don’t need to remember them. Imagine we needed to add a fourth friend to the patterns mentioned in the previous paragraphs. It is equally possible to reach “A *DBC” as it is possible to reach “AC *DB”. In both situations, we are adding D to the left of the second cluster.
Let’s represent the state just by the number of friends already added and the number of clusters. Solve a function f(k,g)
where k
is the number of friends we have already added and g
the current number of clusters. How many final setups will there be after we add the remaining K - k
friends?
Base case: K = k
. We have added all friends. If g = 5
, for example, the pattern will be something like “X *XX *XXX *X *XX” there are 5 gaps and we need to distribute N - K
empty spaces between them. The result is ((N - K -1),(g -1))
. Note that there is a special case: N = K
, then there is a single cluster and there are no separations.
Otherwise, we have many options: Merge two clusters, extend the size of one of the clusters (to the left or to the right), create a new cluster. Always being careful that the gap lengths are limited. For example, count the number of ways to add a new cluster: We have g
options for the position of the new cluster. The number of clusters will increment and we have added one more friend: g f(k + 1, g + 1)
. We should make sure that g < G
, so that we don’t break the number of clusters rule. Another issue is that sometimes the maximum length of the gaps wouldn’t really allow creating a new cluster, so we should cut cases in which the number of friends and separations is too large for N
.
Initially, we place A in a fixed position, we have a single friend and 1 group, so f(1,1)
will solve the problem.
The result is an O(KG)
dynamic programming algorithm.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
const int MOD = 1000000007;
int C[2001][2001];
long mem[2001][2001];
int N, K, G;
long sub(int s, int t) {
if (s == 0) {
return ((t != 0) ? 1 : 0);
} else {
// distribute s elements in t slots such that each slot contains one
return C[s - 1][t - 1];
}
}
long f(int k, int g) {
long & res = mem[k][g];
if (res == -1) {
if ((g >= 2) && (k + g > N)) {
res = 0;
} else {
if (k == K) {
// distribute (N - k) empty spaces in g separators such
// that each has at least 1 element:
res = sub(N - k, g);
} else {
res = 0;
// a) new group There are g spaces where we could place this
if (g < G) {
res += (g * f(k + 1, g + 1)) % MOD;
}
// b) extend an already-existing group.
if ((g == 1) && (k == N - 1) && (K == N)) {
res += f(k + 1, g);
} else {
res += (2 * g * f(k + 1, g)) % MOD;
}
// c) Merge two groups
if (g >= 2) {
res += (g * f(k + 1, g - 1)) % MOD;
}
}
}
res %= MOD;
}
return res;
}
int countseatnumb(int N, int K, int G) {
this - > N = N;
this - > K = K;
this - > G = G;
memset(C, 0, sizeof(C));
for (int i = 0; i <= N; i++) {
C[i][0] = 1;
for (int j = 1; j <= i; j++) {
C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % MOD;
}
}
memset(mem, -1, sizeof(mem));
// don't forget to multiply by N
return (int)((N * f(1, 1)) % MOD);
}